/*
 * Game project submission for:
 *  Class CSE 486 A of Miami University, Fall 2012
 *  
 * Created by:
 *  Reuben Smith (smithre5)
 *  Michael Jacobs (jacobsm)
 *  Jiang Nuo (jiangn)
 */

/* MIT License
 * 
 * Copyright (c) 2012 Reuben Smith, Michael Jacobs, Jiang Nuo, Miami University
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights 
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
 * copies of the Software, and to permit persons to whom the Software is 
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in 
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
 * THE SOFTWARE.
 */

package breakthrough;


import game.GameMove;
import game.GamePlayer;
import game.GameState;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;


// smithre5: This has fallen behind in updates versus the threaded version. Just
// a heads up for those looking to use this.


/**
 * An extremely intelligent Breakthrough AI. You can tell by the use of X.
 * 
 * @author smithre5, jacobsm, jiangn
 */
public class XiBreakthroughPlayer extends GamePlayer
{
	/* FIELDS **************************************************************** */

	// smithre5: Since this is static and constant, most Java compilers will
	// optimize away any code wrapped in if (DEBUG) { ... } if it's false.
	// It's a nice way to leave in debug code without a preprocessor.
	protected static final boolean	DEBUG = false;

	// smithre5: These numbers could probably still use some tweaking. MAKE SURE
	// THAT PRUNING AND ADJUSTING ARE TURNED ON AND AT REASONABLES VALUES AT THE
	// TIME OF SUBMISSION. Note to self.
	protected static final boolean	SEARCH_ADJUST = true;
	protected static final double	SEARCH_ADJUST_UP = 0.25;
	protected static final double	SEARCH_ADJUST_DOWN = 1.05;
	protected static final int		SEARCH_DEPTH_START = SEARCH_ADJUST ? 0 : 4;
	protected static final int		SEARCH_DEPTH_STOP = 16;
	protected static final boolean	SEARCH_PRUNE = true;

	// smithre5: Most games actually seem to only go out to about 30 something
	// moves, but it doesn't hurt (much) to under shoot the time. It'd hurt a
	// lot more to over shoot it.
	protected static final int		AVERAGE_MOVES = 50;
	// smithre5: Update this as features are added.
	protected static final int		FEATURE_COUNT = 10;
	protected static final int		WIN_SCORE = Integer.MAX_VALUE;

	protected Random				generator;

	protected int					averageMoves;
	protected int					movesTaken;
	protected int					movesTakenSum;
	protected int					currentRound;

	protected int					gameTimeLimit;
	protected int					moveTimeLimit;
	protected double				targetMoveTime;

	protected int					depthLimit;
	protected double				depthAdjustUp;
	protected double				depthAdjustDown;

	protected ArrayList<int[]>		features;

	protected String				opponentName;
	protected String				opponentMessage;

    /* TYPES ***************************************************************** */

    /**
     * Utility class encapsulating points of interest for getStateScore.
     */
    protected class EvalVars
    {
        public boolean hasWon;
        
        public int  goalDelta;
        public int  goalDistance;
        public int  goalRow;

        public int  pieces;
        public int  conflict;
        public int  cover;

        public char symbol;


        /**
         * Fills variables with appropriate initial values for the side given.
         * 
         * @param side
         *            the side to be evaluated
         */
        public EvalVars(GameState.Who side)
        {
            if (GameState.Who.HOME == side) {
                goalDelta = +1;
                goalRow = BreakthroughState.N - 1;
                symbol = BreakthroughState.homeSym;
            }
            else {
                goalDelta = -1;
                goalRow = 0;
                symbol = BreakthroughState.awaySym;
            }

            hasWon = false;
            goalDistance = BreakthroughState.N;
            pieces = 0;
            conflict = 0;
            cover = 0;
        }
    }
    
    
    // smithre5: Maybe look into creating a few of these and marking them static
    // final to be used as preset difficulties?
    public static class AIParams
    {
        public long seed;
        public int[] weights;
        
        
        public AIParams(long seed, int[] weights)
        {
            this.seed = seed;
            this.weights = weights;
        }
    }
    

    /* METHODS *************************************************************** */

    /**
     * Default constructor.
     */
    public XiBreakthroughPlayer()
    {
        // smithre5: isDeterministic = false?
        super("Xi", new BreakthroughState(), false);
        generator = new Random();
        
        // smithre5: Build a feature set prior to using gSS to keep brittle code
        // there from breaking.
        features = new ArrayList<int[]>();
        for (int i = FEATURE_COUNT; --i >= 0;) {
            features.add(new int[]{ 1, 0 });
        }
    }
    
    
    /**
     * Parameterized AI constructor.
     * 
     * @param params initial values for AI
     */
    public XiBreakthroughPlayer(AIParams params)
    {
        this();
        
        // This is to allow the user to specify parameters without affecting the
        // randomness of the AI.
        if (params.seed != 0) {
            generator.setSeed(params.seed);
        }
        
        if (params.weights != null) {
            int fwSize = Math.min(params.weights.length, features.size());
            
            for (int i = 0; i < fwSize; ++i) {
                features.get(i)[0] = params.weights[i];
            }
            
            for (int i = features.size() - fwSize; --i >= 0;) {
                features.get(i)[0] = 0;
            }
        }
    }
    

    /**
     * Pre-tournament handling.
     */
    public void init()
    {
        // smithre5: Something more general than per-opponent data could be
        // loaded here. Maybe some initialization for data structures?
    	
    	averageMoves = AVERAGE_MOVES;
    	movesTaken = 0;
    	movesTakenSum = 0;
    	currentRound = 0;
    }


    /**
     * Post-tournament handling.
     */
    public void done()
    {
        // smithre5: Write out data to files here?
    }


    /**
     * Pre-game handling.
     * 
     * @param opponentName
     *            the name of the opponent
     */
    public void startGame(String opponentName)
    {
        // smithre5: This could be used to load a per-opponent play book.

        this.opponentName = opponentName;
        
        depthLimit = SEARCH_DEPTH_START;
        depthAdjustUp = SEARCH_ADJUST_UP;
        depthAdjustDown = SEARCH_ADJUST_DOWN;
        
        movesTakenSum += movesTaken;
        averageMoves = (averageMoves + movesTakenSum) / ++currentRound;
        movesTaken = 0;
        
        if (targetMoveTime != 0) {
        	targetMoveTime = moveTimeLimit / (double)averageMoves;
        }
        
        System.out.println("averageMoves = " + averageMoves);
    }


    /**
     * Post-game handling. Gives the result for the previous game.
     * 
     * @param result
     *            -1 for loss, 0 for draw, +1 for win
     */
    public void endGame(int result)
    {
        // smithre5: This can be used in longer tournaments for learning how
        // a particular player fights and adjusting feature weights. Not sure
        // how effective this could be in a 10-round tourney, though.
    }


    /**
     * Stores message from opponent.
     * 
     * @param message
     *            the message from the opponent
     */
    public void messageFromOpponent(String message)
    {
        // smithre5: This is only used for messageForOpponent. However, these
        // methods could be used in some interesting ways if Xi vs Xi comes up.
        // For example, they could teach each other about fighting other
        // opponents by storing play data in opponent messages. That's for
        // another time, though.

        this.opponentMessage = message;
    }


    /**
     * Returns a human-readable message for the opponent.
     * 
     * @param opponentName
     *            the name of the opponent
     * @return a (witty?) message to the opponent
     */
    public String messageForOpponent(String opponentName)
    {
        // smithre5: Not necessary, but it's a point for a bit of fun.

        String[] messages = new String[] {
                String.format("Hello, %s. Nice to beat you.", opponentName),
                String.format("Why, if it isn't %s.", opponentName),
                String.format("Did you hear? %s lost in the semi-finals. ...sorry. Didn't see you there.", opponentName),
                String.format("'%s', you say? I'm going to pummel you for that, %s.", opponentMessage, opponentName) };

        return messages[generator.nextInt(messages.length)];
    }


    /**
     * Gives in seconds the time taken for the last move.
     * 
     * @param seconds
     *            the time taken in seconds
     */
    public void timeOfLastMove(double seconds)
    {
    	if (SEARCH_ADJUST) {
    		if (depthLimit < SEARCH_DEPTH_STOP && seconds < depthAdjustUp * targetMoveTime) {
    			++depthLimit;
    		}
    		else if (seconds > depthAdjustDown * targetMoveTime) {
    			--depthLimit;
    			
    			if (seconds * AVERAGE_MOVES > depthAdjustDown * gameTimeLimit) {
    				depthAdjustUp *= 1.0 / depthAdjustDown;
    			}
    		}
    	}
    }


    /**
     * Returns the move to be made next.
     * 
     * This method either performs or invokes the methods necessary to perform
     * the logic in deciding the player's next move.
     * 
     * @param state
     *            the state of the game (board information)
     * @param lastMv
     *            the opponent's move preceding this
     * @return the move to be made
     */
    @Override
    public GameMove getMove(GameState state, String lastMv)
    {    	
    	if (targetMoveTime == 0) {
    	    // smithre5: Still not 100% on the differences here.
    		moveTimeLimit = Math.min(BreakthroughState.gameParams.integer("MOVETIME"), 
    				BreakthroughState.gameParams.integer("MAXMOVETIME"));
    		
    		gameTimeLimit = BreakthroughState.gameParams.integer("GAMETIME");
    		
    		targetMoveTime = moveTimeLimit / (double)averageMoves;
    	}
    	
    	// smithre5: Both sides move, hence 2.
    	movesTaken += 2;
    	
        return getBestMove((BreakthroughState)state);
    }


    /**
     * Returns the move considered best for the given state.
     * 
     * @param state
     *            the state to search from
     * @return the best move, ever
     */
    protected BreakthroughMove getBestMove(final BreakthroughState state)
    {        
        ArrayList<BreakthroughMove> moves = getLegalMoves(state);
        BreakthroughMove bestMove = null;
        
        if (DEBUG) {
            bestMove = moves.get(0);
        }
        else {
            bestMove = moves.get(generator.nextInt(moves.size()));
        }
        
        if (depthLimit <= 0) {
            return bestMove;
        }
        
        int bestScore = -WIN_SCORE;
        
        for (BreakthroughMove move : moves) {
            BreakthroughState successor = (BreakthroughState)state.clone();
            successor.makeMove(move);

            int score = -getMoveScore(successor, depthLimit - 1, -WIN_SCORE, WIN_SCORE);

            if (score > bestScore) {
                bestMove = move;
                bestScore = score;
            }
        }

        return bestMove;
    }


    /**
     * Returns the results of a negamax with alpha-beta search from the given
     * state.
     * 
     * @param state
     *            the state to be searched from
     * @param depth
     *            the remaining depth
     * @param alpha
     *            the alpha cut-off
     * @param beta
     *            the beta cut-off
     * @return the score for the given state
     */
    protected int getMoveScore(final BreakthroughState state, int depth, int alpha, int beta)
    {        
    	if (depth == 0 || state.getStatus() != GameState.Status.GAME_ON) {
            return getStateScore(state);
        }

        ArrayList<BreakthroughMove> moves = getOrderedMoves(getLegalMoves(state));

        for (BreakthroughMove move : moves) {
            BreakthroughState successor = (BreakthroughState)state.clone();
            successor.makeMove(move);
            
            /*
             * smithre5: Just so I don't forget, here's how the reduction for
             * this works:
             * 
             * 1. foreach (move): 
             * 2.   score = -getMoveScore( ... ) 
             * 3.   if (score > a) 
             * 4.     a = score 
             * 5.   if (score >= b) 
             * 6.     return a 
             * 7. return a
             * 
             * We can replace (2) with a = max(a, -getMoveScore( ... )) because
             * of (3) and (4) -- a is assigned score when score is bigger than
             * a. This is the same as saying a = a if score < a or a = score if
             * score >= a.
             * 
             * Since score has been transformed into a, we can replace the use
             * of score in (5) with a, giving us if (a >= b) { ... }. The return
             * in (6) can be replaced with a break because (7) already returns
             * a.
             */

            alpha = Math.max(alpha, -getMoveScore(successor, depth - 1, -beta, -alpha));
            
            if (SEARCH_PRUNE && alpha >= beta) {
                break;
            }
        }

        return alpha;
    }


    /**
     * Evaluates the given state and scores it.
     * 
     * @param state
     *            the state to be evaluated
     * @return the given state's score
     */
    protected int getStateScore(final BreakthroughState state)
    {        
        EvalVars player = new EvalVars(state.getWho());
        EvalVars opponent = new EvalVars(state.getWho() == GameState.Who.HOME ? GameState.Who.AWAY : GameState.Who.HOME);
       
        populateEvalVars(state, player, opponent);
        
        if (player.hasWon) {
            return WIN_SCORE;
        }
        else if (opponent.hasWon) {
            return -WIN_SCORE;
        }        
        
        // smithre5: This is brittle. Keep a mental note that it should never be
        // the case that f >= FEATURE_COUNT when using get().
        int f = 0;
        features.get(f++)[1] = player.pieces;
        features.get(f++)[1] = -opponent.pieces;
        features.get(f++)[1] = opponent.goalDistance * opponent.goalDistance;
        features.get(f++)[1] = -(player.goalDistance * player.goalDistance);
        
        //player line penetrated (-)
        //opponent line penetrated (+)
        //player squares owned (+)
        //opponent squares owned (-)
        //cover stuff
        //conflict

        int score = 0;
        for (int i = features.size(); --i >= 0;) {
            score += features.get(i)[0] * features.get(i)[1];
        }
        
        return score;
    }
    
    
    /**
     * Examines the given state and provides evaluation variable data for both
     * sides.
     * 
     * @param state the state examined
     * @param player the current player's perspective
     * @param opponent the opponent's perspective
     * @return true if population finished successfully; false otherwise
     */
    protected boolean populateEvalVars(final BreakthroughState state, EvalVars player, EvalVars opponent)
    {
        if (state == null || player == null || opponent == null) {
            return false;
        }
        
        for (int row = 0; row < BreakthroughState.N; ++row) {
            for (int col = 0; col < BreakthroughState.N; ++col) {
                
            	if (state.board[row][col] == player.symbol) {
                    ++player.pieces;
                    
                    if (player.goalRow == row) {
                        player.hasWon = true;
                        return true;
                    }
                    
                    int nextRow = row + player.goalDelta;
                    int rowTest = BreakthroughState.N - nextRow - 1;
                    if (rowTest >= 0 && rowTest < BreakthroughState.N) {
                        int leftCol = col - 1,
                            rightCol = col + 1;
                        
                        if (leftCol >= 0) {
                            if (state.board[nextRow][leftCol] == player.symbol) {
                                ++player.cover;
                            }
                            else if (state.board[nextRow][leftCol] == opponent.symbol) {
                                ++player.conflict;
                                ++opponent.conflict;
                            }
                        }
                        if (rightCol < BreakthroughState.N) {
                            if (state.board[nextRow][rightCol] == player.symbol) {
                                ++player.cover;
                            }
                            else if (state.board[nextRow][rightCol] == opponent.symbol) {
                                ++player.conflict;
                                ++opponent.conflict;
                            }
                        }
                    }
                }
                else if (state.board[row][col] == opponent.symbol) {
                    ++opponent.pieces;
                    
                    if (opponent.goalRow == row) {
                        opponent.hasWon = true;
                        return true;
                    }
                    
                    int nextRow = row + opponent.goalDelta;
                    int rowTest = BreakthroughState.N - nextRow - 1;
                    if (rowTest >= 0 && rowTest < BreakthroughState.N) {
                        int leftCol = col - 1,
                            rightCol = col + 1;
                        
                        if (leftCol >= 0) {
                            if (state.board[nextRow][leftCol] == opponent.symbol) {
                                ++opponent.cover;
                            }
                        }
                        if (rightCol < BreakthroughState.N) {
                            if (state.board[nextRow][rightCol] == opponent.symbol) {
                                ++opponent.cover;
                            }
                        }
                    }
                }
            }
        }
        
        if (player.pieces == 0) {
            opponent.hasWon = true;
        }
        else if (opponent.pieces == 0) {
            player.hasWon = true;
        }
        
        return true;
    }


    /**
     * Generates a list of all legal moves for the state's active player.
     * 
     * @param state
     *            the game state to be examined
     * @return an ArrayList of legal moves for the given state
     */
    protected final ArrayList<BreakthroughMove> getLegalMoves(final BreakthroughState state)
    {        
        // smithre5: Using 4.5 here (or 75%) since most situations will never
        // actually reach b_max. Tests on 1,000 round tournaments only reached
        // 65-70% of b_max. This gives a slight performance boost.
        ArrayList<BreakthroughMove> moves = new ArrayList<BreakthroughMove>((int)(4.5f * BreakthroughState.N));

        // Initial values for sanity checks in debugging.
        char pSymbol = '?';
        int pDelta = 0;

        if (state.getWho() == GameState.Who.HOME) {
            pSymbol = BreakthroughState.homeSym;
            pDelta = +1;
        }
        else {
            pSymbol = BreakthroughState.awaySym;
            pDelta = -1;
        }

        for (int row = 0; row < BreakthroughState.N; ++row) {
            for (int col = 0; col < BreakthroughState.N; ++col) {
                // skip non-player pieces
                if (state.board[row][col] != pSymbol) {
                    continue;
                }

                int nextRow = row + pDelta;
                int leftCol = col - 1;
                int rightCol = col + 1;

                // can move piece?
                if (nextRow >= 0 && nextRow < BreakthroughState.N) {
                    char[] rowContents = state.board[nextRow];

                    // can move forward?
                    if (rowContents[col] == BreakthroughState.emptySym) {
                        moves.add(new BreakthroughMove(row, col, nextRow, col));
                    }

                    // can move left?
                    if (leftCol >= 0 && rowContents[leftCol] != pSymbol) {
                        moves.add(new BreakthroughMove(row, col, nextRow, leftCol));
                    }

                    // can move right?
                    if (rightCol < BreakthroughState.N && rowContents[rightCol] != pSymbol) {
                        moves.add(new BreakthroughMove(row, col, nextRow, rightCol));
                    }
                }
            }
        }

        return moves;
    }
    
    
    /**
     * Performs optimal move ordering on a collection of moves.
     * 
     * @param moves the moves to be ordered
     * @return a collection of ordered moves
     */
    protected ArrayList<BreakthroughMove> getOrderedMoves(ArrayList<BreakthroughMove> moves)
    {
        if (DEBUG) {
            return moves;
        }
        
        // smithre5: Random move ordering. So not really that optimal. 
        Collections.shuffle(moves, generator);
        
        return moves;
    }
    

    /**
     * Runs the player.
     * 
     * @param args
     *            command-line arguments to the player
     */
    public static void main(String[] args)
    {
        GamePlayer p = new XiBreakthroughPlayer();
        p.compete(args);    
    }
}
